1. Field of the Invention
The present invention relates to queue servicing. More specifically, generating a queue service sequence to determine the particular order in which queues are serviced.
2. Background
Queues are used to temporarily store data awaiting transmission or processing by another device or system. Systems may be connected to receive data from multiple queues. Each queue may handle or represent a particular class or type of data traffic. For example, one queue might receive real-time audio or video signals having a high priority while other queues may receive data having a lower priority and not requiring immediate servicing.
Various systems have been developed to service multiple queues having different priorities. A known queue servicing procedure utilizing strict priority always services the highest priority queue first. If all data in the highest priority queue has been processed, then the next highest priority queue will be serviced. However, if the highest priority queue always contains data to be processed, then the lower priority queues may never be serviced. This may result in lower priority queues filling with data which is never processed, not processed in a timely manner, or discarded. Even the second highest priority queue will not be serviced if the highest priority queue always contains data cells awaiting processing. To avoid this problem, some round-robin queue servicing systems require that lower priority queues be serviced at regular intervals, regardless of the existence of data in the higher priority queues. This method ensures that all queues will be serviced, although the servicing may be relatively infrequent.
Another system for servicing queues assigns a weight to each queue. This weight represents the relative frequency with which the queue is serviced. For example, a high priority queue may be weighted such that it receives 70% of the servicing time available while lower priority queues receive the remaining 30% of the servicing time. Thus, the higher priority queues are assigned higher weights to provide greater servicing times for handling the important data.
Another queue servicing procedure may be referred to as "asynchronous time sharing" and is described in Real Time Scheduling with OOS Constraints, Jay Hyman et al, IEEE Journal on Selected Areas of Communications, vol. 9, Sep. 1991. This procedure assigns a particular period of time for processing each queue which is proportional to the weight of the queue. For example, a particular system receives data from three queues, labeled A, B, and C. Queue A has a weight of 7, queue B has a weight of 3 and queue C has a weight of 2. During a particular time period providing twelve queue servicing operations, the pattern of queue service might be: AAAAAAABBBCC. This procedure provides for servicing of the various queues in proportion to their weights, but does not consider problems created by jitter. Jitter is caused by non-uniform servicing of the queues. In the above example, queue A is serviced for seven consecutive time periods, but is not serviced again for the next five time periods. If queue A is transmitting real-time data such as audio or video data, then the transmitted sound or image may not be smooth because certain data cells are not handled in a timely manner; e.g., the five time periods when queues B and C are being serviced. The data from each queue is transmitted in bursts, with significant delays between the bursts. In the case of real-time data transmission, it is important to use a queue servicing procedure providing relatively constant and small queue interservice times. Therefore, this servicing procedure and the additional procedures discussed above do not reduce jitter in the data flowing from the queues.